/* 用单链表保存m个整数，并且|data|<=n，要求设计时间复杂度尽可能高效的算法，对于data 绝对值相等的点，仅保留第一次出现的点 */
#include <iostream>
#include "headfun.h"
using namespace std;

// 去除绝对值相等的结点
void fun(LNode *&head, int n)
{
  LNode *p = head;
  LNode *r;
  int *q = new int[n + 1];
  int m;
  
  // 初始化长度为n的数组 -- 用于去重
  for (int i = 0; i < n + 1; ++i)
    q[i] = 0;
  
  // 遍历列表
  while (p->next != NULL)
  {
    // 计算绝对值
    if (p->next->data > 0)
      m = p->next->data;
    else
      m = -p->next->data;
    
    // 如果绝对值不重复
    if (q[m] == 0)
    {
      q[m] = 1;
      p = p->next;
    }
    
    // 如果绝对值重复，删除结点
    else
    {
      r = p->next;
      p->next = r->next;
      free(r);
    }
  }
  free(q);
}

int main()
{
  // 创建链表
  LNode *L = head_Linklist();
  
  // 去除绝对值相等的点
  fun(L, 50);
  
  // 遍历链表并打印
  L = L->next;
  while (L != NULL)
  {
    cout << L->data << " ";
    L = L->next;
  }
}